package com.mamingchao.issue.one;

import org.springframework.util.StopWatch;
import org.springframework.util.StringUtils;

import java.util.Arrays;
import java.util.Hashtable;

/**
 * ���ִ���ʽ��
 * 1��������ʽ��һ��һ���ı�����
 * 2��hash ������
 *
 * �򵥴ֱ��� ��ʽ���������ﲻ��������ֱ�� ��hash��ʽ
 *
 * ����һ��hash ӳ�� keyΪ valueֵ�� valueֵΪ ����ֵ��index
 * key    value
 * 15       0
 * 11       1
 * 7        2
 * 2        3
 * 3        4
 * 4        5
 * 5        6
 *
 * Ȼ�� �� target(9) - key(15)�� ��� target-key == key1, key1Ҳ�� hash��key�У���ô key ��key1���� ��
 * ���  target(9) - key(15) �Ľ��(key1)������ hash���棬�ͻ�target(9) - key(11)
 * ��������Ŀ��� 9-15 = -6��
 * Created by mlamp on 2024/6/27.
 */
public class FindTwoNumsSumEqualstarget {

    public static void main(String[] args) {
        final int target = 9;

        int[] arr = {15,11,7,2,3,4};

        System.out.println(Arrays.toString(getTwoNums(arr, target)));


    }

    private static int[] getTwoNums(int[] arr, int target) {

        StopWatch stopWatch = new StopWatch();
        stopWatch.start("��ʼ��������ֵ");
        int[] result = new int[2];

        Hashtable<Integer,Integer> table = new Hashtable <>();

        // �����������ֵ���ŵ�hashtable�key �� �����ֵ��value����index
        for (int i = 0; i < arr.length; i++) {
            table.put(arr[i],i);
        }

        for (int i = 0; i < arr.length; i++) {
            // target - ��ǰ��ֵ == �����ֵ
            int parternerKey = target - arr[i];
            // ��ǰֵ��Ӧ��index Ϊ i


            // ��� hash������ �� �������ֵ�� ���� �������ֵ�� ������ǰ��ֵ������ͬһ����������
            if (table.containsKey(parternerKey) ) {
                //�������ֵ����index
                int parternerIndex = table.get(parternerKey);
                if (i !=  parternerIndex) {
                    result[0] = i;
                    result[1] = parternerIndex;
                }
            } else {
                continue;
            }
        }
        stopWatch.stop();

        System.out.println(String.format("����-{}", stopWatch ) );
        System.out.println("����" + stopWatch);

        return result;
    }
}
